package sort;

public class CountSort {
    public static void countSort(int[] arr){
        //找最大最小值
        int minNum = arr[0];
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] < minNum){
                minNum = arr[i];
            }
            if(arr[i] > maxNum){
                maxNum = arr[i];
            }
        }
        //计数数组
        int[] count = new int[maxNum - minNum +1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]-minNum]++;
        }
        //排序
        int i =0;
        for (int j = 0; j < count.length; j++) {
            while(count[j] > 0){
                arr[i++] = j+minNum;
                count[j]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {6,1,6,3,4,2,10};
        countSort(arr);
        for (int e:
             arr) {
            System.out.print(e+" ");
        }
    }
}
